home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 401-425 / disk_419 / yacc / src.lzh / Src / RCS / closure.c,v < prev    next >
Text File  |  1990-07-14  |  5KB  |  291 lines
  1. head     1.1;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.1
  10. date     90.07.14.18.55.16;  author loftus;  state Exp;
  11. branches ;
  12. next     ;
  13.  
  14.  
  15. desc
  16. @@
  17.  
  18.  
  19.  
  20. 1.1
  21. log
  22. @Initial revision
  23. @
  24. text
  25. @#include "defs.h"
  26.  
  27. short *itemset;
  28. short *itemsetend;
  29. unsigned *ruleset;
  30.  
  31. static unsigned *first_derives;
  32. static unsigned *EFF;
  33.  
  34.  
  35. set_EFF()
  36. {
  37.     register unsigned *row;
  38.     register int symbol;
  39.     register short *sp;
  40.     register int rowsize;
  41.     register int i;
  42.     register int rule;
  43.  
  44.     rowsize = WORDSIZE(nvars);
  45.     EFF = NEW2(nvars * rowsize, unsigned);
  46.  
  47.     row = EFF;
  48.     for (i = start_symbol; i < nsyms; i++)
  49.     {
  50.     sp = derives[i];
  51.     for (rule = *sp; rule > 0; rule = *++sp)
  52.     {
  53.         symbol = ritem[rrhs[rule]];
  54.         if (ISVAR(symbol))
  55.         {
  56.         symbol -= start_symbol;
  57.         SETBIT(row, symbol);
  58.         }
  59.     }
  60.     row += rowsize;
  61.     }
  62.  
  63.     reflexive_transitive_closure(EFF, nvars);
  64.  
  65. #ifdef    DEBUG
  66.     print_EFF();
  67. #endif
  68. }
  69.  
  70.  
  71. set_first_derives()
  72. {
  73.   register unsigned *rrow;
  74.   register unsigned *vrow;
  75.   register int j;
  76.   register unsigned mask;
  77.   register unsigned cword;
  78.   register short *rp;
  79.  
  80.   int rule;
  81.   int i;
  82.   int rulesetsize;
  83.   int varsetsize;
  84.  
  85.   rulesetsize = WORDSIZE(nrules);
  86.   varsetsize = WORDSIZE(nvars);
  87.   first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  88.  
  89.   set_EFF();
  90.  
  91.   rrow = first_derives + ntokens * rulesetsize;
  92.   for (i = start_symbol; i < nsyms; i++)
  93.     {
  94.       vrow = EFF + ((i - ntokens) * varsetsize);
  95.       cword = *vrow++;
  96.       mask = 1;
  97.       for (j = start_symbol; j < nsyms; j++)
  98.     {
  99.       if (cword & mask)
  100.         {
  101.           rp = derives[j];
  102.           while ((rule = *rp++) >= 0)
  103.         {
  104.           SETBIT(rrow, rule);
  105.         }
  106.         }
  107.  
  108.       mask <<= 1;
  109.       if (mask == 0)
  110.         {
  111.           cword = *vrow++;
  112.           mask = 1;
  113.         }
  114.     }
  115.  
  116.       vrow += varsetsize;
  117.       rrow += rulesetsize;
  118.     }
  119.  
  120. #ifdef    DEBUG
  121.   print_first_derives();
  122. #endif
  123.  
  124.   FREE(EFF);
  125. }
  126.  
  127.  
  128. closure(nucleus, n)
  129. short *nucleus;
  130. int n;
  131. {
  132.     register int ruleno;
  133.     register unsigned word;
  134.     register unsigned mask;
  135.     register short *csp;
  136.     register unsigned *dsp;
  137.     register unsigned *rsp;
  138.     register int rulesetsize;
  139.  
  140.     short *csend;
  141.     unsigned *rsend;
  142.     int symbol;
  143.     int itemno;
  144.  
  145.     rulesetsize = WORDSIZE(nrules);
  146.     rsp = ruleset;
  147.     rsend = ruleset + rulesetsize;
  148.     for (rsp = ruleset; rsp < rsend; rsp++)
  149.     *rsp = 0;
  150.  
  151.     csend = nucleus + n;
  152.     for (csp = nucleus; csp < csend; ++csp)
  153.     {
  154.     symbol = ritem[*csp];
  155.     if (ISVAR(symbol))
  156.     {
  157.         dsp = first_derives + symbol * rulesetsize;
  158.         rsp = ruleset;
  159.         while (rsp < rsend)
  160.         *rsp++ |= *dsp++;
  161.     }
  162.     }
  163.  
  164.     ruleno = 0;
  165.     itemsetend = itemset;
  166.     csp = nucleus;
  167.     for (rsp = ruleset; rsp < rsend; ++rsp)
  168.     {
  169.     word = *rsp;
  170.     if (word == 0)
  171.         ruleno += BITS_PER_WORD;
  172.     else
  173.     {
  174.         mask = 1;
  175.         while (mask)
  176.         {
  177.         if (word & mask)
  178.         {
  179.             itemno = rrhs[ruleno];
  180.             while (csp < csend && *csp < itemno)
  181.             *itemsetend++ = *csp++;
  182.             *itemsetend++ = itemno;
  183.             while (csp < csend && *csp == itemno)
  184.             ++csp;
  185.         }
  186.  
  187.             mask <<= 1;
  188.             ++ruleno;
  189.         }
  190.     }
  191.     }
  192.  
  193.     while (csp < csend)
  194.     *itemsetend++ = *csp++;
  195.  
  196. #ifdef    DEBUG
  197.   print_closure(n);
  198. #endif
  199. }
  200.  
  201.  
  202.  
  203. finalize_closure()
  204. {
  205.   FREE(itemset);
  206.   FREE(ruleset);
  207.   FREE(first_derives + ntokens * WORDSIZE(nrules));
  208. }
  209.  
  210.  
  211. #ifdef    DEBUG
  212.  
  213. print_closure(n)
  214. int n;
  215. {
  216.   register short *isp;
  217.  
  218.   printf("\n\nn = %d\n\n", n);
  219.   for (isp = itemset; isp < itemsetend; isp++)
  220.     printf("   %d\n", *isp);
  221. }
  222.  
  223.  
  224. print_EFF()
  225. {
  226.     register int i, j, k;
  227.     register unsigned *rowp;
  228.     register unsigned word;
  229.     register unsigned mask;
  230.  
  231.     printf("\n\nEpsilon Free Firsts\n");
  232.  
  233.     for (i = start_symbol; i < nsyms; i++)
  234.     {
  235.     printf("\n%s", symbol_name[i]);
  236.     rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
  237.     word = *rowp++;
  238.  
  239.     mask = 1;
  240.     for (j = 0; j < nvars; j++)
  241.     {
  242.         if (word & mask)
  243.         printf("  %s", symbol_name[start_symbol + j]);
  244.  
  245.         mask <<= 1;
  246.         if (mask == 0)
  247.         {
  248.         word = *rowp++;
  249.         mask = 1;
  250.         }
  251.     }
  252.     }
  253. }
  254.  
  255.  
  256. print_first_derives()
  257. {
  258.   register int i;
  259.   register int j;
  260.   register unsigned *rp;
  261.   register unsigned cword;
  262.   register unsigned mask;
  263.  
  264.   printf("\n\n\nFirst Derives\n");
  265.  
  266.   for (i = start_symbol; i < nsyms; i++)
  267.     {
  268.       printf("\n%s derives\n", symbol_name[i]);
  269.       rp = first_derives + i * WORDSIZE(nrules);
  270.       cword = *rp++;
  271.       mask = 1;
  272.       for (j = 0; j <= nrules; j++)
  273.         {
  274.       if (cword & mask)
  275.         printf("   %d\n", j);
  276.  
  277.       mask <<= 1;
  278.       if (mask == 0)
  279.         {
  280.           cword = *rp++;
  281.           mask = 1;
  282.         }
  283.     }
  284.     }
  285.  
  286.   fflush(stdout);
  287. }
  288.  
  289. #endif
  290. @
  291.